#include "Subdiv.h"
#include <float.h>
#include <math.h>

const STVector3 CatClarkSurface::kUnimplementedVector(0, 0, 0);
const float MaxFaceSize = 0.0f;	// lock face is screen projection is bigger than that 
static bool isTriangleMesh;

// Load your surface from an OBJ input file.
CatClarkSurface::CatClarkSurface(const char* filename) {
  FILE* input = fopen(filename, "r");
  if (!input) {
    fprintf(stderr, "CatClarkSurface could not open OBJ %s\n", filename);
    exit(-1);
  }

  static const int kMaxLine = 1024;
  char lineBuffer[kMaxLine];
  int lineIndex = 0; // for printing error messages

  //
  // Read the file line-by-line
  //
  while (fgets(lineBuffer, kMaxLine, input)) {
    ++lineIndex;
    char* str = strtok(lineBuffer, " \t\n\r");
    //
    // Skip empty or comment lines.
    //
    if (!str || str[0] == '\0' || str[0] == '#')
      continue;
    if (str[0] == 'g' || str[0] == 'o' || str[0] == 's' || strcmp(str, "usemtl") == 0 || strcmp(str, "mtllib") == 0)
      continue;
    //
    // Process other lines based on their commands.
    //
    if (strcmp(str, "v") == 0) {
      // Vertex position line. Read the position data (x, y, z).
      str = strtok(NULL, "");
      STVector3 position;
      sscanf(str, "%f %f %f\n", &position.x, &position.y, &position.z);
      raw_vertices.PushEnd(position);
		} else if (strcmp(str, "vt") == 0)
		{
			// Do nothing, we're not interested in texture
		}
		else if (strcmp(str, "vn") == 0)
    {	
			/*str = strtok(NULL, "");
			STVector3 position;
			sscanf(str, "%f %f %f\n", &position.x, &position.y, &position.z);
			raw_normals.PushEnd(position);			*/
    }
		else if (strcmp(str, "f") == 0) {
      int num_verts = 0;

      for (char* token = strtok(NULL, " \t");
           token != NULL;
           token = strtok(NULL, " \t")) {
        int index;
        int result = sscanf(token, "%d", &index);
        if (result != 1) {
          break;
        }
        num_verts++;
        // Deal with OBJ indexing rules
        if (index < 0) {
          index = raw_vertices.Length() + index;
        } else {
          index -= 1;
        }
        raw_indices.PushEnd(index);
      }

      if (num_verts < 3) {
        fprintf(stderr, "ERROR: CatClarkSurface(%s), Line %d. Invalid Face (%d verts)\n",
                filename, lineIndex, num_verts);
        exit(-1);
      }
      raw_num_verts.PushEnd(num_verts);
			raw_num_faces.PushEnd(1);			// patch contains only one face at first
    } else {
      fprintf(stderr, "Unable to parse line %d: %s (continuing)\n",
              lineIndex, lineBuffer);
    }
  }
  fclose(input);

	if (NumVerticesInFace(0) == 3)
		isTriangleMesh = true;
	else
		isTriangleMesh = false;	
	 
	// setup vbo data 
	vbo_indices = 0;
	vbo_colors = 0;
	vbo_normals = 0;
	vbo_vertices = 0;
	num_vbo_indices = 0;
	vbo_patches = 0;
	num_vbo_patches = 0;
	SetupVBOData();
}

// Save out the subdivided surface
void
CatClarkSurface::SaveOBJ(const char* filename) const {
  FILE* output = fopen(filename, "w");
  for (size_t i = 0; i < NumVertices(); i++) {
    const STVector3& vertex = GetVertex(i);
    fprintf(output, "v %f %f %f\n",
            vertex.x,
            vertex.y,
            vertex.z);
  }

  for (size_t face = 0; face < NumFaces(); face++) {
    int num_verts = NumVerticesInFace(face);
    fprintf(output, "f ");
    for (int i = 0; i < num_verts; i++) {
      fprintf(output, "%d ", 1 + GetVertexIndex(face, i));
    }
    fprintf(output, "\n");
  }
  fclose(output);
}

// Get bounding box of surface
void
CatClarkSurface::GetBounds(STVector3& boundMin, STVector3& boundMax) const {
  boundMin = STVector3( FLT_MAX,  FLT_MAX,  FLT_MAX);
  boundMax = STVector3(-FLT_MAX, -FLT_MAX, -FLT_MAX);
  for (size_t i = 0; i < NumVertices(); i++) {
    const STVector3& v = GetVertex(i);
    for (int c = 0; c < 3; c++) {
      boundMin.Component(c) = std::min(boundMin.Component(c),
                                       v.Component(c));
      boundMax.Component(c) = std::max(boundMax.Component(c),
                                       v.Component(c));
    }
  }
}

// Subdivide the surface several times
void
CatClarkSurface::Subdivide(int iterations) {
  for (int i = 0; i < iterations; i++) {
    SubdivideOnce2();
  }
}

// Draw the surface at the current level of subdivision
void
CatClarkSurface::Draw() const {
	//if (!isTriangleMesh)
		//DrawQuads();
	//else
		DrawTriangles();
}

void 
CatClarkSurface::DrawTriangles() const {
	glBegin(GL_TRIANGLES);

	int faceIndex = 0;
	for (int k = 0; k < NumPatches(); k++)
	{
		// color is the position of the first vertex in the patch
// 		STVector3 p = GetVertex(GetVertexIndex(faceIndex, 0));
// 		p.Normalize();
	//	glColor3f(0.7, 0.5, 0.3);

		for (size_t face = 0; face < NumFacesInPatch(k); face++) 
		{
			int num_verts = NumVerticesInFace(faceIndex);
			int a = GetVertexIndex(faceIndex, 0);
			int b = GetVertexIndex(faceIndex, 1);
			for (int i = 2; i < num_verts; i++) {
				int c = GetVertexIndex(faceIndex, i);
				STVector3 N = STVector3::Cross(GetVertex(b) - GetVertex(a),
					GetVertex(c) - GetVertex(a));
				glNormal3f(N.x, N.y, N.z);
				int indices[3] = {a, b, c};
				for (int v = 0; v < 3; v++) {
					const STVector3& posn = GetVertex(indices[v]);
					glVertex3f(posn.x, posn.y, posn.z);
					// printf("face %i v1 %f v2 %f v3 %f \n", face, posn.x, posn.y, posn.z);
					// printf("face index a %i \n", indices[v]);
				}
				b = c;
			}

			faceIndex++;
		}
	}
	glEnd();
}

// Draw the surface at the current level of subdivision
void
CatClarkSurface::DrawQuads() const {
	
	bool gl_line_mode = false;
	if (glIsEnabled(GL_POLYGON_OFFSET_LINE) == GL_TRUE)
		gl_line_mode = true;

	glBegin(GL_QUADS);
	
	int faceIndex = 0;
	for (int k = 0; k < NumPatches(); k++)
	{
		// color is the position of the first vertex in the patch
		STVector3 p = GetVertex(GetVertexIndex(faceIndex, 0));
		p.Normalize();
		float r = floor(rand()%1000/200.0f)/5.f;
		float g = floor(rand()%1000/200.0f)/5.f;
		float b = floor(rand()%1000/200.0f)/5.f;

		if (gl_line_mode)
			glColor3f(0.2, 0.2, 0.2);

		for (size_t face = 0; face < NumFacesInPatch(k); face++) 
		{
			int num_verts = NumVerticesInFace(faceIndex);
			int a = GetVertexIndex(faceIndex, 0);
			int b = GetVertexIndex(faceIndex, 1);
			int c = GetVertexIndex(faceIndex, 2);
			int d = GetVertexIndex(faceIndex, 3);
			STVector3 N = STVector3::Cross(GetVertex(b) - GetVertex(a),
				GetVertex(c) - GetVertex(a));
			glNormal3f(N.x, N.y, N.z);
			int indices[4] = {a, b, c, d};
			for (int v = 0; v < 4; v++) 
			{
				const STVector3& posn = GetVertex(indices[v]);
				glVertex3f(posn.x, posn.y, posn.z);
				// printf("face %i v1 %f v2 %f v3 %f \n", face, posn.x, posn.y, posn.z);
				// printf("face index a %i \n", indices[v]);
			}

			faceIndex++;
		}	
	}

	glEnd();
}

// Run your subdivision pipeline once
void
CatClarkSurface::SubdivideOnce() {
  // following
  BuildMesh();
  ComputeFacePoints();
  ComputeEdgePoints();
  ComputeVertexPoints();
  ConnectVertices();
	SetupVBOData();
}


void
CatClarkSurface::SubdivideOnce2() {
	// following
	BuildMesh();
	ComputeFacePoints();
	ComputeEdgePoints2();
	ComputeVertexPoints2();
	ConnectVertices();
	SetupVBOData();
}

// Build any mesh data structures you need to
void
CatClarkSurface::BuildMesh() {

	vertices.Reserve(NumVertices());
	patches.Reserve(NumPatches());
	edges.Reserve(NumFaces()*2);

	int faceIndex = 0;
	// setup patch for each face and insert to patch structure
	for (int k = 0; k < NumPatches(); k++)
	{
		Patch* patch = new Patch();
		for (int i = 0; i < NumFacesInPatch(k); i++)
		{
			Face* face = new Face();
			for (int j =0; j < NumVerticesInFace(faceIndex); j++)
			{
				// create vertex
				STVector3 s = GetVertexOfFace(faceIndex,j);
				STVector3 e = GetVertexOfFace(faceIndex, (j+1)%NumVerticesInFace(faceIndex));

				Vertex* vs = findVertex(s);
				Vertex* ve = findVertex(e);

				if (vs == NULL)
				{
					vs = new Vertex(s);
					vertices.PushEnd(vs);
				}

				if (ve == NULL)
				{
					ve = new Vertex(e);
					vertices.PushEnd(ve);
				}

				vs->addFace(face);

				// create edge
				Edge* edge = findEdge(vs->pos, ve->pos);
				if (edge == NULL)
				{
					edge = new Edge(vs, ve);
					edge->setLFace(face);
					edges.PushEnd(edge);
					vs->addEdge(edge);
					ve->addEdge(edge);

					// printf("new edge at face %i, edge %i with vs %i vj %i\n", faceIndex, j, vs, ve);
				}
				else 
				{
					edge->setRFace(face);
				}

				face->addEdge(edge);

			}

			faceIndex++;
			face->setBBSize(checkBBoxSize(face));	
			patch->addFaces(face);
		}

		patches.PushEnd(patch);
	}
}

void CatClarkSurface::SetupVBOData()
{
	if(vbo_vertices != 0) delete vbo_vertices;
	if(vbo_normals != 0) delete vbo_normals;
	if(vbo_indices != 0) delete vbo_indices;
	if(vbo_colors != 0) delete vbo_colors;
	if(vbo_patches != 0)	delete vbo_patches;

	num_vbo_patches = raw_num_faces.Length();
	num_vbo_indices = 0;

	// number of indices
	for (size_t face = 0; face < NumFaces(); face++) 
	{
		int num_verts = NumVerticesInFace(face);
		num_vbo_indices += (num_verts-2)*3;
	}
	
	int numVertices = NumVertices();
	
	vbo_vertices =  new GLfloat[num_vbo_indices*3];
	vbo_normals = new GLfloat[num_vbo_indices*3];
	vbo_colors = new GLfloat[num_vbo_indices*3];
	vbo_indices = new GLuint[num_vbo_indices];
	vbo_patches = new GLuint[num_vbo_patches];
	
	// copy the vertices firstly
	for (int i = 0; i < raw_vertices.Length(); i++)
	{	
		vbo_vertices[i*3] = (GLfloat)raw_vertices[i].x;
		vbo_vertices[i*3+1] = (GLfloat)raw_vertices[i].y;
		vbo_vertices[i*3+2] = (GLfloat)raw_vertices[i].z;
		//printf("vertices %i x %f y %f z %f \n", i, vbo_vertices[i*3], vbo_vertices[i*3+1], vbo_vertices[i*3+2]);
	}

	// wrong code for triangles, but some times the indices from obj files are in quad form.
	//for (int i = 0; i < raw_indices.Length(); i++)
	//{
	//	vbo_indices[i] = raw_indices[i];
	//	printf("indices %i %i \n", i, vbo_indices[i]);
	//}
	
	// copy number of faces per patch, split quad into triangles
	int face_index = 0;
	for (size_t patch = 0; patch < num_vbo_patches; patch++)
	{
		int num_faces = raw_num_faces[patch];
		int num_triangles = 0;
		for (int i = 0; i < num_faces; i++)
		{	
			int num_verts = NumVerticesInFace(face_index);
			num_triangles += (num_verts-2);
		}
		vbo_patches[patch] = num_triangles;
		face_index += num_faces;
	}

	face_index = 0;
	int n_index = 0;
	for (int k = 0; k < NumPatches(); k++)
	{
		float color_r = 1.0;//floor(rand()%1000/200.0f)/5.f;
		float color_g = 1.0;//floor(rand()%1000/200.0f)/5.f;
		float color_b = 1.0;//floor(rand()%1000/200.0f)/5.f;

		for (size_t face = 0; face < NumFacesInPatch(k); face++) 
		{
			int num_verts = NumVerticesInFace(face_index+face);
		
			int a = GetVertexIndex(face_index+face, 0);
			int b = GetVertexIndex(face_index+face, 1);
			for (int i = 2; i < num_verts; i++) 
			{
				int c = GetVertexIndex(face_index+face, i);
				STVector3 N = STVector3::Cross(GetVertex(b) - GetVertex(a),
					GetVertex(c) - GetVertex(a));
				
				int indices[3] = {a, b, c};
				for (int v = 0; v < 3; v++) 
				{
					vbo_indices[n_index+v] = indices[v];

					const STVector3& posn = GetVertex(indices[v]);
				
					vbo_vertices[(n_index+v)*3] = posn.x;
					vbo_vertices[(n_index+v)*3+1] = posn.y;
					vbo_vertices[(n_index+v)*3+2] = posn.z;

					vbo_normals[(n_index+v)*3] = N.x;
					vbo_normals[(n_index+v)*3+1] = N.y;
					vbo_normals[(n_index+v)*3+2] = N.z;

					vbo_colors[(n_index+v)*3] = color_r;
					vbo_colors[(n_index+v)*3+1] = color_g;
					vbo_colors[(n_index+v)*3+2] = color_b;
					//printf("face %i with color  %f  %f  %f \n", face, r, g, b);
				// printf("face index a %i \n", indices[v]);
				}
				b = c;
				n_index +=3;
			}
		}
		face_index += NumFacesInPatch(k);
	}
}

// Now that all the new positions are computed, compute the
// corresponding topology and prepare your mesh for the next round of
// subdivision/display.
void
CatClarkSurface::ConnectVertices() 
{
	raw_vertices.FreeMemory();
	raw_indices.FreeMemory();
	raw_num_verts.FreeMemory();
	raw_num_faces.FreeMemory();

	int numFaces = 0;
	for (int i = 0; i < patches.Length(); i++)
		numFaces+=patches[i]->numFaces();

	raw_indices.Reserve(numFaces*4*4);
	raw_vertices.Reserve(vertices.Length()*4+2);
	raw_num_verts.Reserve(vertices.Length()*4);
	raw_num_faces.Reserve(patches.Length());	// patches do not change length

	// refresh the raw data to render. 
	int faceIndex = 0;
	for (int i = 0; i < patches.Length(); i++)
	{	
		raw_num_faces.PushEnd(patches[i]->numFacesAfterSubdv());

		Vector<Face*> faces = patches[i]->getFaces();
		for (int j = 0; j < faces.Length(); j++)
		{
			// for the locked faces, dont't apply subdivision at all.
			if (faces[j]->isLocked())
			{
				int edge_num = faces[j]->getNumEdge();
				raw_num_verts.PushEnd(edge_num);
				for(int k = 0; k < edge_num; k++)
				{
					STVector3 sv = faces[j]->getEdge(k)->startV(faces[j])->getVertexPoint();
					// printf("SV %i pre EV %i \n", sv, faces[i]->preEdge(j)->endV(faces[i]));
					raw_indices.PushEnd(insertVertex(sv));	
				}
			}
			else		// the unlocked the faces, apply the normal subdivision
			{
				int edge_num = faces[j]->getNumEdge();
				for(int k = edge_num -1 ; k >= 0; k--)
				{
					STVector3 sv = faces[j]->getEdge(k)->startV(faces[j])->getVertexPoint();
					STVector3 ep = faces[j]->getEdge(k)->getEdgePoint();
					STVector3 fp = faces[j]->getFacePoint();
					STVector3 pre_ep = faces[j]->preEdge(k)->getEdgePoint();

					// printf("SV %i pre EV %i \n", sv, faces[i]->preEdge(j)->endV(faces[i]));

					raw_num_verts.PushEnd(4);
					raw_indices.PushEnd(insertVertex(sv));
					raw_indices.PushEnd(insertVertex(ep));
					raw_indices.PushEnd(insertVertex(fp));
					raw_indices.PushEnd(insertVertex(pre_ep));
				}
			}
		}
	}

	// DeleteMemory the old mesh now 
	patches.DeleteMemory();
	edges.DeleteMemory();
	vertices.DeleteMemory();
}


// CS148 TODO: Implement these helper functions for your mesh.
unsigned int
CatClarkSurface::NumFaces() const {
  return raw_num_verts.Length();
}

unsigned int 
CatClarkSurface::NumPatches() const {
	return raw_num_faces.Length();
}

unsigned int
CatClarkSurface::NumVertices() const {	
  return raw_vertices.Length();
}

unsigned int
CatClarkSurface::NumIndices() const {	
	return raw_indices.Length();
}

unsigned int
CatClarkSurface::NumVerticesInFace(unsigned int face) const {
  return raw_num_verts[face];
}

unsigned int 
CatClarkSurface::NumFacesInPatch(unsigned int patch) const {
	return raw_num_faces[patch];
}

unsigned int
CatClarkSurface::GetVertexIndex(unsigned int face, unsigned int v) const {
  int index = 0;
  for(int i = 0; i < face; i++)
    index += raw_num_verts[i];
  return raw_indices[index + v];
}

const STVector3&
CatClarkSurface::GetVertex(unsigned int i) const {
	//printf("get vertex at %i value %f %f %f \n", i, raw_vertices[i].x, raw_vertices[i].y, raw_vertices[i].z);
  return raw_vertices[i];
}

const STVector3&
CatClarkSurface::GetVertexOfFace(unsigned int face, unsigned int v) const {
  // printf("get vertex at face %i, v %i final index %i \n", face, v, GetVertexIndex(face, v));
	return GetVertex(GetVertexIndex(face, v));
}

// Compute the centroid of all faces in the mesh (face points)
void
CatClarkSurface::ComputeFacePoints() 
{
	// loop all the faces
	for (int i = 0; i < patches.Length(); i++)
	{
		Vector<Face*> fs = patches[i]->getFaces();
		for (int j = 0; j < fs.Length(); j++)
		{
			fs[j]->computeFacePoint();
		}
	}
}

// Compute the Catmull Clark edge points for each edge (the average
// of the two edge endpoints and the two adjacent face points).
void
CatClarkSurface::ComputeEdgePoints() 
{
	for (int i = 0; i < edges.Length(); i++)
	{
		edges[i]->computeEdgePoint();	
	}
}

void
CatClarkSurface::ComputeEdgePoints2() 
{
	for (int i = 0; i < edges.Length(); i++)
	{
		edges[i]->computeEdgePoint2();	
	}
}

// Compute the new position of each original vertex. This value is
// an averaging of the face points, the edge points and the original
// vertex.
void
CatClarkSurface::ComputeVertexPoints() 
{
	for (int i = 0; i < vertices.Length(); i++)
	{
		vertices[i]->computeVertexPoint();
	}
}

void
CatClarkSurface::ComputeVertexPoints2() 
{
	for (int i = 0; i < vertices.Length(); i++)
	{
		vertices[i]->computeVertexPoint2();
	}
}

void Face::computeFacePoint()
{
	STVector3 p(0, 0, 0);
	for(int i = 0; i < edges.Length(); i++)
	{
		p += edges[i]->startV(this)->pos;
	}

	fp = p/edges.Length();
}

void Edge::computeEdgePoint()
{
	/* ((v0 + v1)/2 + (left face + right face)/2)/2
	 average of the two vertices and center of two faces
	 for the cases with boundaries, (v0 + v1)/2, ignore faces */
	if (isBoundary())
	{
		ep = (vs->pos + ve->pos)/2;
	}
	else 
	{
		ep = (vs->pos + ve->pos + lFace->getFacePoint() + rFace->getFacePoint())/4;
	}

	//ep = (vs->pos + ve->pos)/2;
}

void Edge::computeEdgePoint2()
{
	// ((v0 + v1)/2 + (left face + right face)/2)/2
	// average of the two vertices and center of two faces
	// for the cases with boundaries, (v0 + v1)/2, ignore faces 
	//if (isBoundary())
	//{
	//	ep = (vs->pos + ve->pos)/2;
	//}
	//else 
	//{
	//	ep = (vs->pos + ve->pos + lFace->getFacePoint() + rFace->getFacePoint())/4;
	//}

	ep = (vs->pos + ve->pos)/2;
}

void Vertex::computeVertexPoint()
{
	// (-Q + 4E + (n-3)*S)/n - for noboundary
	// S/2 + M/4 - for meshes with boundary

	//vp = pos;

	int boundaries = 0;
	STVector3 M(0, 0, 0); // 

	for (int i = 0; i < valence(); i++)
	{
		Edge* e = edges[i];
		if (e->isBoundary())
		{
			M += e->getEdgePoint();
			boundaries++;
		}
	}

	if (boundaries > 0)
	{
		vp = pos/2 + M/boundaries/2;
	}
	else
	{
		// average face point connecting to this vertex;
		STVector3 Q(0, 0, 0);
		for (int j = 0; j < faces.Length(); j++)
		{
			Q += faces[j]->getFacePoint();
		}
		Q /= faces.Length();

		// the average of the newly computed edge points connected
		STVector3 E(0, 0, 0);
		for (int j = 0;j < edges.Length(); j++)
		{
			E += edges[j]->getEdgePoint();
		}
		E /= edges.Length(); 

		vp = (-Q + 4*E + (valence()-3)*pos)/valence();
	}
}

void Vertex::computeVertexPoint2()
{
	// (-Q + 4E + (n-3)*S)/n - for noboundary
	// S/2 + M/4 - for meshes with boundary

	vp = pos;

	//int boundaries = 0;
	//STVector3 M(0, 0, 0); // 

	//for (int i = 0; i < valence(); i++)
	//{
	//	Edge* e = edges[i];
	//	if (e->isBoundary())
	//	{
	//		M += e->getEdgePoint();
	//		boundaries++;
	//	}
	//}

	//if (boundaries > 0)
	//{
	//	vp = pos/2 + M/boundaries/2;
	//}
	//else
	//{
	//	// average face point connecting to this vertex;
	//	STVector3 Q(0, 0, 0);
	//	for (int j = 0; j < faces.Length(); j++)
	//	{
	//		Q += faces[j]->getFacePoint();
	//	}
	//	Q /= faces.Length();

	//	// the average of the newly computed edge points connected
	//	STVector3 E(0, 0, 0);
	//	for (int j = 0;j < edges.Length(); j++)
	//	{
	//		E += edges[j]->getEdgePoint();
	//	}
	//	E /= edges.Length(); 

	//	vp = (-Q + 4*E + (valence()-3)*pos)/valence();
	//}
}

float CatClarkSurface::checkBBoxSize(Face* f)
{
	float minx, maxx, maxy, miny;	// left, right, up, down
	minx = FLT_MAX; maxx = -FLT_MAX;	// shit code here
	miny = FLT_MAX; maxy = -FLT_MAX;

	for (int i = 0; i < f->getNumEdge(); i++)
	{
		STVector3 vpos = f->getEdge(i)->startV(f)->pos;		// start vertex of the edge
		GLdouble ov[3] = {vpos.x, vpos.y, vpos.z};
		GLdouble sv[3];
		// convert to screen space
		gluProject(ov[0], ov[1], ov[2], model, project, view, &sv[0], &sv[1], &sv[2]);
		STVector3 v(sv[0], sv[1], sv[2]);

		minx = MIN(minx, v.x);
		miny = MIN(miny, v.y);
		maxx = MAX(maxx, v.x);
		maxy = MAX(maxy, v.y);
	}

	return (maxx-minx)*(maxy-miny);
	
		/*printf("input point %f %f %f \n", ov1[0], ov1[1], ov1[2]);
		printf("input point %f %f %f \n", ov2[0], ov2[1], ov2[2]);
		printf("input point %f %f %f \n", ov3[0], ov3[1], ov3[2]);*/

		//printf("new screen point %f %f %f \n", sv1[0], sv1[1], sv1[2]);
		//printf("new screen point %f %f %f \n", sv2[0], sv2[1], sv2[2]);
		//printf("new screen point %f %f %f \n", sv3[0], sv3[1], sv3[2]);
}

// WE mesh function
Edge* CatClarkSurface::findEdge(const STVector3 &s, const STVector3 &e)
{
	for (int i=0; i < edges.Length(); i++)
	{
		if (edges[i]->reverseEqual(s, e))
			return edges[i];
	}
	return NULL;
}

bool Edge::reverseEqual(const STVector3 &s, const STVector3 &e)
{
	return (vs->pos == e && ve->pos == s);
}

Vertex* CatClarkSurface::findVertex(STVector3 v)
{
	for (int i=0; i < vertices.Length(); i++)
	{
		if (vertices[i]->pos == v)
			return vertices[i];
	}
	return NULL; 
}

unsigned int CatClarkSurface::insertVertex(STVector3 v)
{
	// insert if not exist, return index
	for(int i = 0; i < raw_vertices.Length(); i++)
		if (raw_vertices[i] == v)
			return i;

	raw_vertices.PushEnd(v);
	return raw_vertices.Length()-1;
}

//////////////////////////////////////////////////////////////////////////
bool Edge::isBoundary()
{
	if (lFace == NULL || rFace == NULL)
		return true;
	else if (lFace->isLocked() || rFace->isLocked())
		return true;
	else 
		return false;
}

bool Face::hasVertex(Vertex* v)
{
	for(int i = 0; i < edges.Length(); i++)
	{
		if( edges[i]->startV(this) == v)
			return true;
	}

	return false;
}

void Face::setBBSize(float s)
{
	BBSize = s;
	if (BBSize < MaxFaceSize)
	{
		locked = true;
	}
}

Edge* Face::preEdge(int j)
{
	if (j < 1)
		return edges[edges.Length()-1];
	else
		return edges[j-1];
}

// return vs when face is null
Vertex* Edge::startV(Face* face)
{
	if (face == rFace)
		return ve;
	else 
		return vs;
}	

// return ve when face is null
Vertex* Edge::endV(Face* face)
{
	if (face == rFace)
		return vs;
	else
		return ve;
}

void Patch::addFaces(Face* f)
{
	faces.PushEnd(f);
}

int Patch::numFacesAfterSubdv()
{
	int num = 0;
	for (int i = 0; i < faces.Length(); i++)
	{
		if (faces[i]->isLocked())
			num+=1;
		else 
			num+=4;
	}

 return num;
}